#include <iostream>
#include <cstring>
#include <cmath>
#include <vector>

int const maxn = 131072 + 4;
int const max_prime_num = 12251 + 4;
short power[max_prime_num][maxn];
short st[max_prime_num][maxn][17 + 4];
int mo = 1000000007;

std::vector<int> prime;

int n, m;

void init_prime()
{
	bool not_prime[maxn];
	std::memset(not_prime, 0, sizeof(not_prime));
	for (int i = 2; i < maxn; i++) {
		if (!not_prime[i]) prime.push_back(i);
		for (int j = 2*i; j < maxn; j += i) not_prime[j] = true;
	}
}

void break_down(int k, int x)
{
	for (int i = 0; i < (int)prime.size(); i++) {
		int p = prime[i];
		for (; !(x % p); x /= p) power[i][k]++;
		if (x == 1) break;
	}
}

void init_st()
{
	for (int pi = 0; pi < (int)prime.size(); pi++) {
		for (int i = 0; i < n; i++)
			st[pi][i][0] = power[pi][i];
		for (int len = 1; (1<<len) <= n; len++) {
			for (int i = 0; i < n; i++)
				st[pi][i][len] = std::max(st[pi][i][len-1], st[pi][i+len][len-1]);
		}
	}
}

int quick(int x, int y)
{
	if (y == 0) return 1;
	int tmp = quick(x, y/2);
	tmp *= tmp;
	if (y & 1) tmp *= x;
	return tmp;
}

int ask_st(int k, int l, int r)
{
	int len = std::log(double(r-l))/std::log(double(2));
	return std::max(st[k][l][len], st[k][r-len][len]);
}

int main()
{
	std::ios::sync_with_stdio(false);
	init_prime();
	int T;
	std::cin >> T;
	for (int ti = 1; ti <= T; ti++) {
		std::cout << "Case #" << ti << ":\n";
		std::memset(power, 0, sizeof(power));

		std::cin >> n >> m;
		for (int i = 0, t; i < n; i++) {
			std::cin >> t;
			break_down(i, t);
		}

		init_st();

		for (int i = 0, l, r; i < m; i++) {
			std::cin >> l >> r;
			int ans = 1;
			for (int j = 0; j < (int)prime.size(); j++) {
				int t = ask_st(j, l-1, r);
				ans *= quick(prime[j], t);
			}
			std::cout << ans % mo << '\n';
		}
	}
}

